package solution.design;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zhangmin
 * @create 2021-10-18 13:31
 *
 * 设计问题：295. 数据流的中位数
 * 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
 * 本题的核心思路是使用两个优先级队列。
 */
public class MedianFinder {

    private PriorityQueue<Integer> large;
    private PriorityQueue<Integer> small;

    public MedianFinder() {
        // 小顶堆:存放前一半的元素
        large=new PriorityQueue<>();
        // 大顶堆：存放后一半的元素
        small=new PriorityQueue<>((o1, o2) -> o2-o1);
    }

    //从数据流中添加一个整数到数据结构中。
    // 不仅要维护large和small的元素个数之差不超过 1，还要维护large堆的堆顶元素要大于等于small堆的堆顶元素。
    public void addNum(int num) {
        //想要往large里添加元素，不能直接添加，而是要先往small里添加，然后再把small的堆顶元素加到large中；向small中添加元素同理。
        if (small.size()>=large.size()){
            //需要向large中添加元素，但是不直接添加，而是要先往small里添加，然后再把small的堆顶元素加到large中
            small.offer(num);
            large.offer(small.poll());
        }else {
            large.offer(num);
            small.offer(large.poll());
        }
    }

    //返回目前所有元素的中位数。
    public double findMedian() {
        // 如果元素不一样多，多的那个堆的堆顶元素就是中位数
        if (large.size()<small.size()){
            return small.peek();
        }else if (large.size()>small.size()){
            return large.peek();
        }
        // 如果元素一样多，两个堆堆顶元素的平均数是中位数
        return (large.peek()+small.peek())/2.0;
    }
}
